package com.zk.algorithm.tree;

import com.zk.algorithm.Utils;
import com.zk.algorithm.bean.TreeNode;
import com.zk.algorithm.factory.TreeFactory;

/**
 * 二叉树的最小深度 https://leetcode.com/problems/minimum-depth-of-binary-tree/
 *
 * @author zk
 */
public class MinimumDepthOfBinaryTree {

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = minDepth(root.left);
        int right = minDepth(root.right);

        // ================
        // 总之最后都要对结果 +1，因为当前 root 节点占有一层
        // ================

        return (left == 0 || right == 0) ?
                left + right + 1 :
                Math.min(left, right) + 1;
    }

    public static void main(String...args) {
        int minDepth = new MinimumDepthOfBinaryTree().minDepth(TreeFactory.buildTree(new Integer[]{
                3, 9, 20, null, null, 15, 7
        }));

        System.out.println(minDepth);
    }

}
